package 优势洗牌;

import java.util.*;

/**
 * 优势洗牌
 * 给定两个大小相等的数组 A 和 B，A相对于B的优势可以用满足A[i] > B[i]的索引的i的数目来描述。
 * 返回A的任意排列，使其相对于B的优势最大化。
 */
public class Solution {
    public static void main(String[] args) {

        int[] a = {10, 24, 8, 32};
        int[] b = {13, 25, 25, 11};
        int[] res = bf(a, b);
        System.out.println("res = " + Arrays.toString(res));


    }

    private static int[] bf(int[] a, int[] b) {

        int[] bClone = b.clone();

        quickSort(bClone);
        quickSort(a);

        Map<Integer, Deque<Integer>> map = new HashMap<>();

        for (int i : b) {
            map.putIfAbsent(i, new LinkedList<>());
        }

        Deque<Integer> aq = new LinkedList<>();

        int j = 0;
        for (int v : a) {
            if (v > bClone[j]) {
                map.get(bClone[j++]).add(v);
            } else {
                aq.add(v);
            }
        }

        int[] res = new int[a.length];
        for (int i = 0; i < b.length; i++) {
            if (!map.get(b[i]).isEmpty()) {
                res[i] = map.get(b[i]).removeLast();
            } else {
                res[i] = aq.remove();
            }
        }

        return res;
    }

    static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    static void quickSort(int[] arr, int start, int end) {

        if (start >= end) return;

        int v = arr[start];
        int l = start;
        int r = end;

        while (l < r) {
            while (l < r && arr[r] >= v) r--;
            swp(arr, r, l);

            while (l < r && arr[l] <= v) l++;
            swp(arr, r, l);
        }

        quickSort(arr, start, l - 1);
        quickSort(arr, l + 1, end);

    }

    private static void swp(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

}
